一、題目介紹
今天要練習的題目是LeetCode 733：Flood Fill

題目會給我們一個二維圖片image，每個位置代表一個像素的顏色，另外給定起始位置(sr, sc)與新的顏色color
我們需要從起始位置開始，將與起始像素連通且顏色相同的區域全部改成新的顏色

例如：
image =
[
[1, 1, 1],
[1, 1, 0],
[1, 0, 1]
]

sr = 1
sc = 1
color = 2

從中間的1開始進行 Flood Fill，與它上下左右相連、且原本顏色也是1的區域都會被改成2

結果：
[
[2, 2, 2],
[2, 2, 0],
[2, 0, 1]
]

這題的核心就是：從一個位置出發，不斷搜尋與它相鄰、符合條件的位置
因此可以使用DFS（Depth-First Search）或BFS（Breadth-First Search）

二、解題思路
首先記錄起始位置原本的顏色：originalColor = image[sr][sc]
接著從(sr, sc)開始搜尋

每個位置最多往四個方向移動

也就是
(-1, 0)
(1, 0)
(0, -1)
(0, 1)

搜尋新的位置時，需要確認

1. 沒有超出圖片範圍
2. 該位置的顏色與originalColor相同
3. 符合條件後，把它改成新的color
4. 繼續搜尋它的四個方向
   這樣就能把整個連通區域找出來

三、為什麼需要特別處理顏色相同？
這裡有一個很重要的小細節

假設
originalColor = 1
color = 1
也就是說，起始顏色和新的顏色完全相同

如果我們直接進行DFS
把 1 改成 1
↓
繼續搜尋
↓
還是看到 1
↓
繼續搜尋
↓
可能不斷重複

因此必須先判斷(Java)
if (originalColor == color) {
return image;
}

Python也是相同概念
這是一個很容易忽略，但非常重要的邊界情況

四、Java實作DFS

五、Python實作DFS

六、BFS的另一種解法
除了DFS，也可以使用BFS（Breadth-First Search）

DFS是：一條路走到底，再回頭尋找其他路
BFS則是：先處理目前位置，再一層一層往外擴散

Flood Fill使用BFS時，可以利用Queue
起點
↓
第一層相鄰位置
↓
第二層相鄰位置
↓
繼續向外擴散

Java BFS

這裡有一個很重要的技巧
image[newRow][newCol] = color;
queue.offer(new int[]{newRow, newCol});

加入Queue的同時就先改顏色
這樣可以避免同一個位置被重複加入Queue

七、Java與Python解法比較

八、時間與空間複雜度
假設圖片大小為m × n

時間複雜度：O(m × n)

• 最壞情況下，整張圖片的每個像素都需要被拜訪一次

空間複雜度：O(m × n)

• DFS本身不需要額外建立陣列，但是使用遞迴呼叫時，最壞情況下可能有大量遞迴層數。
• 例如整張圖片都是同一種顏色，就可能需要搜尋整個區域。

九、DFS與BFS的比較

這題使用DFS會比較簡潔，但如果未來遇到「最短距離、最少步數、按層搜尋」等問題，BFS通常會更加適合

十、實作結果
Leetcode測試結果：Accepted

十一、今日學習心得
今天的Flood Fill讓我第一次比較完整地接觸DFS和BFS的搜尋概念。以前看到二維陣列時，通常會想到利用雙層迴圈逐格處理，但Flood Fill並不是單純把每個位置都走過一次，而是要從指定位置開始，尋找與它相連且符合條件的區域。

透過DFS，我了解到可以從一個位置開始，不斷往上下左右四個方向搜尋，直到遇到邊界或不同顏色的位置。另一方面，BFS則可以利用Queue一層一層向外擴散，兩種方法都能完成相同的Flood Fill任務。

這次也讓我注意到「拜訪過的位置要避免重複處理」非常重要。將已經處理過的像素直接改成新的顏色，就可以同時當作搜尋過的記號，避免同一個位置不斷被加入搜尋流程。

經過今天的練習，我開始理解DFS / BFS不只是用在樹或圖上，也可以應用在二維矩陣、迷宮、地圖與區域搜尋等問題。這讓我對之後的Number of Islands也有了比較好的基礎。